In many communication systems, such as wireless systems, the transmission channel varies unpredictably over time and the transmitter in the system cannot know in advance the quality of the channel. Various phenomena, such as thermal noise, multipath fading, Doppler effects, interference from other transmitters, may be the source of such channel variations and unpredictability of existing channel conditions. Communication systems employ forward error correction (FEC) coding schemes to provide reliable transmission of information over noisy and time-varying communication channels. In FEC schemes, the transmitter encodes input data packets into codewords from an error correcting code and transmits the codewords over the communication channel. The codewords carry redundant information about the input data packets and that redundancy renders the information in the input data packets more resilient against the corruption caused by the channel. The receiver in a FEC scheme is equipped with a decoder that aims to recover the input data packets from channel-corrupted copies of the transmitted codewords. When the channel conditions are worse than usual, e.g., during periods of deep fading, the receiver may fail to recover the input data packets from the corrupted codewords. Even for channels whose statistics are stationary in time, occasionally, the noise in the channel exceeds typical levels and the FEC code proves insufficient to recover the input data packet correctly.
In order to provide reliable communication in an effective manner in the face of adverse channel conditions, many communication systems employ Hybrid Automatic Repeat reQuest (HARQ) methods that combine FEC with error-detection and retransmission. In addition to a forward channel from the transmitter to the receiver, HARQ schemes require a feedback channel from the receiver to the transmitter. The feedback channel is used to send a feedback message that indicates whether the receiver was able to recover the input data packet successfully. In its rudimentary form a feedback message may be a positive acknowledgement (ACK) or a negative acknowledgement (NACK). An ACK indicates that the receiver decoded the current input data packet successfully; a NACK indicates the opposite. There are many varieties of HARQ schemes; a comprehensive discussion of the methods and issues regarding HARQ may be found in the reference [Lin, Chap. 22]. A description of fundamental concepts relating to general HARQ schemes follows.
HARQ schemes process input data packets in HARQ sessions, with each HARQ session comprising the transmission of a primary packet and possibly a number of additional HARQ packets, all derived from the same input data packet. A HARQ session begins with the HARQ transmitter receiving a new input data packet, encoding the input data packet into a primary codeword, placing the primary codeword in a primary packet, and transmitting the primary packet over the forward channel. If the HARQ receiver is able to recover the input data packet from the received primary packet, it sends an ACK; otherwise, it sends a NACK. Whenever the HARQ transmitter receives an ACK, the current HARQ session ends (with success), and a new HARQ session begins as soon as a new input data packet becomes available. Whenever the HARQ transmitter receives a NACK, it checks if the number of transmissions in the current HARQ session has reached a certain limit. If so, the current session terminates with failure; if not, the HARQ transmitter generates a new codeword from the current input data packet, places it in a HARQ packet, and transmits the HARQ packet over the forward channel. Upon receiving a new HARQ packet, the HARQ receiver attempts to recover the input data packet one more time, using the information available in the latest HARQ packet as well as the information in the packets received previously in the current HARQ session.
The limit on the number of packets that can be transmitted in a HARQ session is a design parameter typically determined by latency constraints for the particular type of data that is sent in the HARQ session. For example, real-time applications, such as voice transmission or remote control of machines, are less tolerant of latency, and the limit on the number of packets should be chosen accordingly. Applications such as file transfer to a cloud storage system, on the other hand, can tolerate much higher delays but require virtually error-free recovery of the input data packets, and the limit on the number of packets can be chosen large enough to ensure adequate reliability.
If the limit on the number of transmissions is reached with no ACK message being received by the HARQ transmitter, a communication system constrained mainly by latency may move to the transmission of the next input data packet, while one constrained by reliability may abort operations and send an alarm signal to a higher layer protocol. The specific details on how to handle this type of error event do not constrain the application of the present principles.
HARQ schemes provide reliability through “diversity.” Diversity in HARQ may take the form of simple repetition such as in the “Chase Combining” (CC) method [Chase], or it may take the form of “Incremental Redundancy” (IR). In the CC-HARQ, the HARQ codewords are exact copies of the primary codeword. In IR-HARQ, the HARQ codewords can be any codeword derived from the current input data packet. A special form of providing diversity by IR is rateless coding [Byer]. The relation of rateless coding and HARQ coding is discussed in [Sol].
The present principles are directed primarily at constructing IR-HARQ schemes by using systematic polar codes. Polar codes are a newer type of linear block code introduced in the paper [Arik1], incorporated herein by reference and included in the file history of this application. In systematic codes, the input data packet appears transparently as part of the codeword. Systematic polar codes were first discussed in [Arik2] and recursive methods for systematic encoding of polar codes were disclosed in [Arik3]. Systematic coding has two main advantages in the context of polar coding. It improves the Bit Error Rate (BER) performance of polar codes as shown in [Arik2, Li]; and, it allows construction of “turbo-like” polar codes, as pointed out in [Arik2] and further studied in [Wu]. In fact, these advantages of systematic coding are not specific to polar coding; they hold over other code families, such as convolutional codes, and are well known to practitioners in the field.
Prior work includes numerous HARQ schemes based on polar codes. The proposals in [Chen1], [Moha] study Chase combining with polar codes. The methods in [Chen2], [ElKh], [Feng], [Huaw1], [Li], and [Song] are examples of IR-HARQ schemes. HARQ methods for polar codes involve shortening and puncturing as means of adjusting the length of polar codes to desired values. One method of shortening and puncturing a polar code is described in [Wang]; this method has the advantage of being simple.
The present disclosure proposes a new IR-HARQ method based on systematic polar coding together with shortening and puncturing of polar codes. The present principles can be applied as a HARQ scheme with any type of FEC code for generating a primary codeword. The present principles use systematic polar coding to generate the HARQ codewords. The present principles differ from the prior art in the manner systematic polar coding is used to generate the IR-HARQ codewords. It is an object of the present principles to improve throughput and reliability in transmitting data in a digital communication system. It is an object of the present principles to provide an improved IR-HARQ scheme using systematic polar codes.
Apart from HARQ applications, the present principles can be used as a standalone method for constructing rateless polar codes based on systematic encoding of data. Present principles comprise methods for encoding and decoding of rateless polar codes. It is an object of present principles to provide a rateless polar coding scheme based on systematic encoding of input data.